「国家集训队」数颜色/维护队列

发表于 | 分类于 | | 浏览量： 次

什么？维护序列的题？当然是上莫队啦poi！

传送门

洛谷传送门

BZOJ传送门

题解

很显然这是一道莫队的题呢poi！

但是有修改操作QwQ。

怎么办呢poi？

当然是写一个资瓷修改的莫队啦！(好像都是废话)

首先我们要把所有操作分成两坨，一坨修改操作，一坨询问操作。

并且我们需要预处理出进行每一个修改操作之前这个要修改的位置上的颜色。

还要预处理出进行每一个询问操作时已近完成了几个修改操作。

然后在莫队的时候，如果当前已经进行了的修改操作的个数与当前询问操作所记录的已经进行了的修改操作数不一致，暴力更新一下就行了呢poi！

据说这样带修改的莫队只要把块的大小设置为$n^\frac{2}{3}$就能将时间内复杂度控制在可接受的范围内呢poi。

其他的按照普通莫队写就行啦poi！

还有洛谷上这题数据比较强，如果不按玄学方法排序要吸个氧才能AC(也有可能是蒟蒻我的常数太大了QwQ)。

代码

其实还挺好写的呢poi

还有不要问我为什么那么喜欢poi呢poi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50005;
int n,m,m1,m2,S,A[maxn],B[maxn],Area[maxn],ans[maxn],L,R,now,ncnt,hsh[1000005];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
char GetChar()
{
	char ch=getchar();
	while(ch!='Q'&&ch!='R') ch=getchar();
	return ch;
}
struct Query
{
	int L,R,id,cnt;
	bool operator < (const Query& b)const{return Area[L]<Area[b.L]||(Area[L]==Area[b.L]&&((Area[L]&1)?R>b.R:R<b.R));}
}Q[maxn];
struct Update{int P,C,lst;}U[maxn];
inline void inc(int num){if(!hsh[num]++) now++;}
inline void dec(int num){if(!--hsh[num]) now--;}
int main()
{
	n=read();m=read();S=pow(n,0.666666)+1e-10;
	for(int i=1;i<=n;i++) Area[i]=(i-1)/S+1;
	for(int i=1;i<=n;i++) A[i]=B[i]=read();
	for(int i=1;i<=m;i++)
	{
		if(GetChar()=='Q'){Q[++m1].L=read();Q[m1].R=read();Q[m1].id=m1;Q[m1].cnt=m2;}
		else{U[++m2].P=read();U[m2].C=read();U[m2].lst=B[U[m2].P];B[U[m2].P]=U[m2].C;}
	}
	sort(Q+1,Q+1+m1);
	L=1;R=1;hsh[A[1]]++;now=1;
	for(int i=1;i<=m1;i++)
	{
		while(R<Q[i].R) inc(A[++R]);
		while(L>Q[i].L) inc(A[--L]);
		while(R>Q[i].R) dec(A[R--]);
		while(L<Q[i].L) dec(A[L++]);
		while(ncnt>Q[i].cnt)
		{
			A[U[ncnt].P]=U[ncnt].lst;
			if(L<=U[ncnt].P&&U[ncnt].P<=R){dec(U[ncnt].C);inc(U[ncnt].lst);}
			ncnt--;
		}
		while(ncnt<Q[i].cnt)
		{
			ncnt++;
			A[U[ncnt].P]=U[ncnt].C;
			if(L<=U[ncnt].P&&U[ncnt].P<=R){inc(U[ncnt].C);dec(U[ncnt].lst);}
		}
		ans[Q[i].id]=now;
	}
	for(int i=1;i<=m1;i++) printf("%d\n",ans[i]);
	return 0;
}